package DP.打家劫舍;

import org.junit.Test;

/**
 * 0 和 n-1 不能同时偷 （中间相隔 由之前基础架保证）
 *
 * (略)同时不偷 / 0 or n-1 其一偷
 *
 * -> 以后做题 照着 自己上个题架子 抄 ，不要纯生写 ？
 *
 * [精华]
 *  1） +1 +2 是 拿/不拿 核心
 *  2） 模板 最好 带图！
 *
 */
public class 环形打家劫舍213 {
    int[] p;
    int n;
    int[] map;
    public int rob(int[] nums) {
        p = nums;
        n = nums.length;
        if(n==1) return nums[0]; // [1]-1 [0]-0
        map = new int[n];
        for (int i = 0; i < n; i++) {
            map[i] = -1;
        }

        // 偷0 不偷n-1 -> 0起 到 n-2
        int one = backTrack(0,n-2);

        // 缺： map重新初始化-1
        for (int i = 0; i < n; i++) {
            map[i] = -1;
        }
        // 不偷0 偷n-1 -> 1起 到 n-1
        int two = backTrack(1, n-1);

        return Math.max(one, two);
    }
    private int backTrack(int cI, int finalInd) {
        if(cI >= finalInd+1){
            return 0;
        }


        if(map[cI] != -1){
            return map[cI];
        }

        int tou = backTrack(cI+2, finalInd) + p[cI];
        int butou = backTrack(cI+1,finalInd);

        int curMax = Math.max(tou, butou);
        map[cI] = curMax;
        return curMax;
    }

    @Test
    public void test() {
        System.out.println("RES:" + rob(new int[]{1,2,1,1}));
    }
}
